package com.xy6.struct.graph;

import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Test;

/**
 * 有向图测试用例
 * <pre>
 * DAG: directed acyclic graph
 * </pre>
 * 
 * @author zhang
 * @since 2017-10-02
 */
public class DirectedGraphTest {
	
	DirectedGraph g = new DirectedGraph();
	
	private void init(){
		int[] v = { 0, 1, 2, 3 };
		int[][] e = {{0,1,1,1},{1,0,1,0},{1,1,0,1},{1,0,1,0}};
		g = new DirectedGraph(v, e);
	}
	
	@Test
	public void init21(){
		int[] v = { 0, 1, 2, 3, 4, 5, 6 };
		int[][] e = {{0,1,1,0,0,0,0},{0,0,0,1,1,0,0},{0,0,0,0,0,1,0},{1,0,0,0,0,0,0},{0,1,0,0,0,0,0},{0,0,0,0,0,0,6},{0,0,0,0,0,0,0}};
		g = new DirectedGraph(v, e);
	}
	
	@Test
	public void init31(){
		int[] v = { 0, 1, 2, 3, 4, 5, 6 };
		int[][] e = {{0,1,1,0,0,0,0},{0,0,0,1,1,0,0},{0,0,0,0,0,1,0},{1,1,0,0,0,0,0},{0,1,0,0,0,0,0},{0,0,0,0,0,0,6},{0,0,0,0,0,0,0}};
		g = new DirectedGraph(v, e);
	}
	
	private void init41(){
		int[] v = { 0, 1, 2, 3 };
		int[][] e = {{0,1,1,0},{0,0,1,0},{0,0,0,1},{1,0,0,0}};
		g = new DirectedGraph(v, e);
	}
	
	private void init3(){
		int[] v = { 0, 1, 2, 3, 4, 5 };
		int[][] e = {{0,1,0,1,0,0},{1,0,1,0,0,0},{0,1,0,1,0,0},{1,0,1,0,0,0},{0,0,0,0,0,1},{0,0,0,0,1,0}};
		g = new DirectedGraph(v, e);
	}
	
	private void init4(){
		int[] v = { 0, 1, 2, 3 };
		int[][] e = {{0,1,3,4},{1,0,1,0},{3,1,0,1},{4,0,1,0}};
		g = new DirectedGraph(v, e);
	}
	
	private void init5(){
		int[] v = { 0, 1, 2, 3 };
		int[][] e = {{0,1,0,0},{1,0,1,2},{0,1,0,2},{0,2,2,0}};
		g = new DirectedGraph(v, e);
	}
	
	@Test
	public void testExistLoop1() {
//		String[] graph = { "1,2", "3,4", "5", "0", "1", "6", null };
		init21();
		List<String> rst = g.existLoop();
		assertEquals(2, rst.size());
	}

	@Test
	public void testExistLoop2() {
//		String[] graph = { "1,2", "3,4", "5", "0,1", "1", "6", null };
		init31();
		List<String> rst = g.existLoop();
		assertEquals(3, rst.size());
	}
	
	@Test
	public void testPrint1() {
		init();
		g.print();
	}
	
	@Test
	public void testPrintDegree1(){
		init();
		g.printDegree();
	}
	
	@Test
	public void testDFS21(){
		init21();
		g.iteratorDFS();
	}
	
	@Test
	public void testBFS22(){
		init21();
		g.iteratorBFS();
	}
	
	@Test
	public void testDFS31(){
		init31();
		g.iteratorDFS();
	}
	
	@Test
	public void testBFS32(){
		init31();
		g.iteratorBFS();
	}

	@Test
	public void testGetMinPath1(){
		init41();
		g.getMinPathDFS(0, 3);
	}
	
	@Test
	public void testGetMinPath13(){
		init41();
		g.getMinPathDFS(3, 0);
	}
	
	@Test
	public void testGetMinPath12(){
		init41();
		g.getMinPathDFS(3, 1);
	}
	
	@Test
	public void testGetMinPathDijkstra1(){
		init41();
		g.getMinPathDijkstra(0, 3);
	}
	
	@Test
	public void testGetMinPathDijkstra2(){
		init41();
		g.getMinPathDijkstra(3, 1);
	}
	
	@Test
	public void testGetMinPathDijkstra32(){
		init3();
		g.getMinPathDijkstra(0, 4);
	}
	
	@Test
	public void testGetMinPathDijkstra41(){
		init4();
		g.getMinPathDijkstra(0, 3);
	}
	
	@Test
	public void testGetMinPathDijkstra42(){
		init4();
		g.getMinPathDijkstra(1, 3);
	}
	
	@Test
	public void testGetMinPathDijkstra43(){
		init4();
		g.getMinPathDijkstra(2, 0);
	}
	
	@Test
	public void testGetMinPathDijkstra5(){
		init5();
		g.getMinPathDijkstra(0, 3);
	}
	
}
